package unit13_动态规划.part3_大厂冲刺题;

public class MinDistance {
    public int minDistance(String ss1, String ss2) {
        char[] s1 = ss1.toCharArray();
        char[] s2 = ss2.toCharArray();
        int m = s1.length;
        int n = s2.length;
        int i, j, k;
        int[][] f = new int[m + 1][n + 1];
        for (j = 0; j <= n; j++) {
            f[0][j] = j;
        }
        for (i = 1; i <= m; i++) {
            f[i][0] = i;
            for (j = 1; j <= n; j++) {
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i - 1][j - 1] + 1);
                f[i][j] = Math.min(f[i][j], f[i][j - 1] + 1);

                if (s1[i - 1] == s2[j - 1]) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                }
            }

        }
        return f[m][n];
    }
}
